package tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> r1 = new ArrayList<>();
        ArrayList<Integer> r2 = new ArrayList<>();

        r1 = levelOrder(root1);
        r2 = levelOrder(root2);

        System.out.println(r1);
        System.out.println(r2);

        return r1.equals(r2);
    }

    public ArrayList<Integer> levelOrder(TreeNode root){
        ArrayList<Integer> ret = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode temp = q.pop();

            if(temp.left == null && temp.right == null){
                ret.add(temp.val);
            }

            if(temp.left!=null)
                q.offer(temp.left);

            if(temp.right!=null)
                q.offer(temp.right);
        }

        return ret;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode root1 = new TreeNode(1,node1,node2);
        TreeNode node3 = new TreeNode(3);
//        TreeNode node4 = new TreeNode(2);
        TreeNode root2 = new TreeNode(1);
        root2.left = node3;

        Solution s =new Solution();
        System.out.println(s.leafSimilar(root1, root2));
    }
}